package q139_wordBreak;

import java.util.List;

public class Solution {
    /**
        完全背包问题
        1.定义：boolean dp[i] -> 用字典中的单词能否前i个字符串
        2.递推公式：
        i > j
        如果前j个字符串能够用字典中的词汇拼出(这是前提)
        &&
        从j到i这段字符串能够在字典中找到 -> 说明前i个字符串能够用字典中的词汇拼出
        if(dp[j] == true && wordDict.contains(s.substring(j,i))) -> dp[i] = true
        3.初始化：
        dp[0] = true 空字符串不用字典中的词汇也能拼出 无为而治 同时之后的结果也是以dp[0]为基础 如果为false
        之后的结果也都会为false
        4.遍历顺序：
        这道题理论上先遍历字符串(背包)还是先遍历字典(物品)的结果都是一样的
        只不过因为涉及到子串问题的特殊性 单词的顺序会进行打乱 不会按照字典中的顺序出现
        因此为了方便可以使用先遍历背包再遍历物品的方式
        如果反过来的话 需要先用容器将物品进行存储 较为麻烦
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        //base case
        dp[0] = true;
        //先遍历背包
        for(int i = 1;i <= s.length();i++) {
            // 再遍历物品
            // i和j也可以作为校验字符串是否在字典中存在的双指针
            // 但是规定j小于i
            for(int j = 0;j < i;j++) {
                // 如果s[0...j]之间的字符串能够拼凑出 && s[j...i]之间的字符串也在字典中存在
                if(dp[j] && wordDict.contains(s.substring(j,i))) {
                    // 那么说明s[0...j] + s[j...i] 拼凑出来字符串可以用字典拼出
                    dp[i] = true;
                }
            }

        }
        return dp[s.length()];
    }

}
